\documentclass[11pt]{amsart}
\usepackage{geometry}                % See geometry.pdf to learn the layout options. There are lots.
\geometry{letterpaper}                   % ... or a4paper or a5paper or ... 
%\geometry{landscape}                % Activate for for rotated page geometry
\usepackage[parfill]{parskip}    % Activate to begin paragraphs with an empty line rather than an indent
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{epstopdf}
\DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `dirname #1`/`basename #1 .tif`.png}

\title{Logarithmic Cover Time of a Branching Process on Finite Graphs}
\author{Chinmoy Dutta, Gopal Pandurangan, Rajmohan Rajaraman, and Scott Roche}
%\date{}                                           % Activate to display a given date or no date

\begin{document}
\maketitle

\section{Problem Overview}

Consider the following branching process on a finite graph. Let $G$ be a d-regular random graph, and let $|V(G)|$ = n. Pick an arbitrary vertex, $v \in V(G)$ as the start vertex for the process, and place a pebble on it. For each time step, the process evolves as follows: Each pebble splits into two. Then, each pebble randomly picks of the the neighbors of $v$ and hops to it. If a vertex receives more than one pebble at time $t$, then the two or more pebbles are merged into one. The process repeats until each vertex in the graph has been visited by a pebble at least once. The vertices bear no "memory" -- they can be visited multiple times, with no change in the behavior of the pebbles.

 How long does this process take to cover $G$? It is well known that the cover time of an expander graph (which $G$ of course is) is $O(n \log n)$. This is trivially true for our process as well - there is always at least one pebble hopping around, performing a random walk on $G$. Below we present an $O(\log^2 n)$ bound for the process. The only part of the proof that requires more than $O(\log n)$ time is the second part, in which we calculate how long it would take $\epsilon n$ pebbles, for some $\epsilon < 1$, moving according to our process to cover the graph.


\section{An $O(\log^2 n)$ bound on Cover Time}

The proof of the $\log^2 n$ cover time on $\alpha$-vertex, $\beta$-edge, $\Delta$-regular random graph $G$ is broken up into two phases. In the first phase we prove that for marked sets of size $\le \epsilon n$, for some constant $\epsilon < 1$, the size of the marked set is growing with each step in the process. We show this first in expectation and then set up a martingale argument to show that the growth rate is concentrated around the mean growth rate, with high probability.

In the second phase, we show that our process will cover the entire graph in $\log^2 n$ time by comparing it to a similar, but weaker random process. In this related process we employ a "conservation of pebbles" principle and modify the transition probabilities to make them similar to those of our original process. By showing that the alternate process takes longer than our process but still has an $O(\log^2 n)$ bound we establish the desired result.


\subsection{Phase 1}
In this phase, assume that at each time step we have marked set  $S_t$, and its first-order neighborhood is $N(S_t)$. Here we do not rule out the possibility of a non-empty intersection between $S_t$ and $N(S_t)$.  We want to show that the marked set is growing with each time step by some growth factor greater than one;

%%%%%% Theorem 2.1 %%%%%%%%%%
\newtheorem{th1}{Theorem}[section]
\begin{th1} Let $\epsilon < 1$ , $\delta > 1$ be constants and set $n = |V(G)|$.  Then for $|S_t| \le \epsilon n$,  $|S_{t+1}| \ge \delta |S_t|$ with high probability.
\end{th1}

To prove this, we actually want to look at what is happening to the compliment of the marked set: $N(S_t) - S_{t+1}$, and show that $|N(S_t) - S_{t+1}|  =  |N(S_t)| - |S_{t+1}| \le (\alpha - \delta)|S_t|$, which is equivalent to showing that $|S_{t+1}| \ge \delta |S_t|$.  To prove Theorem 1 we need the following lemmas, from which the proof is immediate.

%%%%%% Lemma 1 %%%%%%%%%%

\newtheorem{lm1}{Lemma}[section]
\begin{lm1}  $E[|N(S_t) - S_{t+1}]| \le (\alpha - \delta)|S_t|$
\begin{proof}
For each vertex $u \in N(S_t)$, we can treat its presence in the unmarked set at time $t+1$ as a Bernoulli random variable with probability $p = (1-\frac{1}{\Delta})^{k d_u}$, where $k$ is the branching factor (which will be 2 for our application) of the process and $d_u$ the number of edges of $u$ that are incident to vertices in $S_t$.  The expectation of this variable is p, so that
\begin{equation} E[|N(S_t) - S_{t+1}|] \le \sum_{u \in N(S_t)} (1 - \frac{1}{\Delta})^{k d_u} \le \sum_{u \in N(S_t)} e^{- \frac{k d_u}{\Delta}}
\end{equation}
Consider the function 
\begin{equation}
f(x) = \sum_{\{1,\dots,n\}} e^{-x_i} \text{ s.t. } 1\le x_i \le \Delta \text{   } \forall i \text{  and  } \sum x_i = A
\end{equation}

Note that $f(x)$, unconstrained, has no critical point, since each component of $\nabla f(x)$ takes on the form $-e^{-x_i}$, which is not equal to zero except at the limit. However, taking constraint $g(x) = \sum x_i - A$ and using the method of Lagrange multipliers for $\nabla f(x) = \lambda \nabla g(x)$ we obtain $[-e^{-x_1},\ldots,-e^{-x_n}] = \lambda [1,\ldots,1]$, which will be satisfied when $x_1 = \ldots = x_n$, which under the constraint $\sum_i x_i = A$ happens only at the mean of the $x^i, \bar{x} = \frac{\sum_i x_i}{n}$. Because the Hessian of $f(x)$ is positive definite, this point is a minimum.

Now consider our function: 
\begin{equation}
f^* (x) = \sum_{u \in N(S_t)} e^{-\frac{k d_u}{\Delta}} 
\end{equation} 
subject to 
\begin{equation*}
\sum_{i \in N(S_t)} d_{u_i} = |E(S_t)| 
\end{equation*}
where $|E(S_t)|$ is the number of edges between $S_t$ and $N(S_t)$. We want to argue that $f^*(x)$ takes on its constrained maximum when there are as many $d_u = 1$ assignments as possible, and the rest are filled by $d_u = \Delta$, with the exception of one remainder value, $d_u = r$ for $0 \le r < \Delta$. Let m be the number of $d_u = \Delta$ assignments and l the number of $d_u = 1$ assignments, and let $\hat{r}$ be the vertex in $N(S_t)$ that takes on $d_u = r$. We therefore need to prove the following four things:
\begin{itemize}
\item That there exist values $m,l,r$ for $k,l$ between 1 and $\Delta$ that satisfy: 
\begin{eqnarray}
m\Delta + l +  r &=& |E(S_t)| \\
m + l + 1 &=& |N(S_t)|.  
\end{eqnarray}
\item Having only one $r$ value maximizes $f^*(x)$. 
\item That assignments for $m,l,r$ that maximize $l$ maximize the function $f^*(x)$.  \\
\item That proving the lemma for the set defined by $N(S_t) - \hat{r} - S_t$ is sufficient for proving the result for $N(S_t) - S_t$.
\end{itemize} 

The first point is true because equations (4) and (5) define two equations for three unknowns. We will always be able to fix $m,l$, and $r$ so that the equalities are satisfied, especially since $r$ is variable. 

The second point has two sub-cases. Both claim that we cannot increase the value of $f*(x)$ by having more than one vertex with "remainder" values.  In the first sub-case, we take one of the $d_u = 1$ vertices and distribute $r+1$ edges between $r_1$ and $r_2$. By a similar argument as that above, $e^{-\frac{k r_1}{\Delta}} + e^{-\frac{k r_2}{\Delta}}$ is minimized subject to $r + 1 = r_1 + r_2$ when $r_1 = r_2 = \frac{r_1 + r_2}{2}$, so to show that $r$ and 1 are the correct values we need to just show that 
\begin{equation*}
e^{-\frac{k r}{\Delta}} + e^{-\frac{k}{\Delta}} > e^{-\frac{k 2}{\Delta}} + e^{-\frac{k (r-1)}{\Delta}}
\end{equation*}
With a little rearranging we have:
\begin{eqnarray*}
e^{-\frac{k}{\Delta}}  - e^{-\frac{k 2}{\Delta}} + e^{-\frac{k r}{\Delta}}  - e^{-\frac{k (r-1)}{\Delta}} &>& 0 \\
\frac{ e^{\frac{k}{\Delta}} -1}{e^{\frac{2k}{\Delta}}} - \frac{e^{\frac{k}{\Delta}} -1}{e^{\frac{r k}{\Delta}}} &>& 0
\end{eqnarray*}
for $r > 2$. In the second sub-case, we take one of the $d_u = \Delta$ vertices and distribute those edges over $r_1,r_2$. Using arguments identical to the first sub-case with $r_1 = \Delta - 1$ and $r_2 = r+1$, we can show that $f^*(x)$ with only one $r$ is greater than $f^*(x)$ with $r_1$ and $r_2$ and one fewer $\Delta$ vertex.

The third point requires more work. Suppose that some assignment to $m,l,r$ that maximizes $l$ is not the maximum for $f^*(x)$. This means that we have to decrease $l$, but we can't do this by a unit value:  we need to decrease l in increments of $\Delta$ in order to still satisfy (4). Let $x^*$ be our original assignment and let $x^{**}$ be our new assignment. Then:
\begin{eqnarray*}
f(x^*) - f(x^{**})  &=& [m  e^{-k} + l e^{-\frac{k}{\Delta}} + e^{-\frac{r}{\Delta}}]  -  [(m+1)  e^{-k} + (l-1) e^{-\frac{k}{\Delta}} + e^{-\frac{r}{\Delta}}] \\
&=& - e^{-k} + e^{-\frac{k}{\Delta}} \\
 &>&  0
\end{eqnarray*}

Thus $x^{**}$ cannot possibly be the maximum, thus proving the third point. 

Finally, consider the set $\widehat{N(S_t)} = N(S_t) - \hat{r}$. If we can prove that  $E[|\widehat{N(S_t)} - S_{t+t}|] \le |\widehat{N(S_t)}|  - \delta |S_t|$, it follows immediately that $E[|N(S_t) - S_{t+1}|] \le |N(S_t)| - \delta |S_t|$ because we are adding only $e^{-\frac{r}{\Delta}}$ to the left hand side and 1 to the right. 

To do this we can modify equation 1 so that we are adding over two "worst-case", disjoint regions of $\widehat{N(S_t)}$ to get a new upper bound:  $R_1$, which contains those vertices that have $d_u = 1$, and $R_2$,  which contains the vertices that have $d_u = \Delta$:
\begin{equation}
E[|\widehat{N(S_t)} - S_{t+1}|] \le \sum_{R_1} e^{- \frac{k}{\Delta}} + \sum_{R_2} e^{-k}
\end{equation} 
Then 
\begin{eqnarray}
|R_1| + |R_2| &=& |\widehat{N(S_t)}| \\
|R_1| + \Delta |R_2| &=& |\widehat{E(S_t)}|
\end{eqnarray}
where $|\widehat{E(S_t)}|$ is the number of edges between $S_t$ and $\widehat{N(S_t)}$. Subtracting (5) from (4) and solving for $|R_1|, |R_2|$ yields:
\begin{eqnarray}
|R_2| &=& \frac{|\widehat{E(S_t)}| - |\widehat{N(S_t)}|}{\Delta - 1} \\
|R_1| &=& |\widehat{N(S_t)}| - \frac{|\widehat{E(S_t)}| - |\widehat{N(S_t)}|}{\Delta -1} = \frac{\Delta |\widehat{N(S_t)}| - |\widehat{E(S_t)}|}{\Delta - 1} 
\end{eqnarray}
Advancing from (10), we have that:
\begin{eqnarray}
E[|\widehat{N(S_t)} - S_{t+1}|] &\le& |R_1|e^{-\frac{k}{\Delta}} + |R_2|e^{-k} \\
&= & \frac{\Delta |\widehat{N(S_t)}| - |\widehat{E(S_t)}|}{\Delta -1} e^{-{k}{\Delta}} + \frac{|\widehat{E(S_t)}| - |\widehat{N(S_t)}|}{\Delta - 1} e^{-k} 
\end{eqnarray}
and want to show that the l.h.s of (11) is:
\begin{equation}
\le |\widehat{N(S_t)}| - \delta |S_t|
\end{equation}

Making use of the expander properties $\alpha_{S_t} |S_{t}| \le |\widehat{N(S_t)}|$ and $\beta_{S_t} |S_{t}| \le |\widehat{N(S_t)}|$, moving $|\widehat{N(S_t)}|$ in (13) over to the other side of the inequality in (12) and doing some rearranging of terms gives us:
\begin{equation}
|\widehat{N(S_t)}| \left[ \frac{\Delta}{\Delta - 1} e^{\frac{-k}{\Delta}} - \frac{1}{\Delta - 1} e^{-k} - 1\right] + |\widehat{E(S_t)}| \left[ \frac{1}{\Delta - 1} e^{-k} - \frac{1}{\Delta - 1} e^{\frac{-k}{\Delta}} \right] \le \delta |S_t|
\end{equation}
 and taking advantage of the the fact that because of this the quantities in both brackets are now negative, we want to find parameters $\alpha,\beta,k$ that will make the following hold while keeping $\delta > 1$;
\begin{eqnarray}
 \alpha_{S_t} |S_{t}| \left[ \frac{\Delta}{\Delta - 1} e^{\frac{-k}{\Delta}} - \frac{1}{\Delta - 1} e^{-k} - 1\right] + \beta_{S_t} |S_{t}|  \left[ \frac{1}{\Delta - 1} e^{-k} - \frac{1}{\Delta - 1} e^{\frac{-k}{\Delta}} \right]  & \le & \delta |S_{t}| \\
 \Rightarrow  \alpha_{S_t} \left[ \frac{\Delta}{\Delta - 1} e^{\frac{-k}{\Delta}} - \frac{1}{\Delta - 1} e^{-k} - 1\right] + \beta_{S_t} \left[ \frac{1}{\Delta - 1} e^{-k} - \frac{1}{\Delta - 1} e^{\frac{-k}{\Delta}} \right]  & \le & -\delta \\
\Rightarrow  \alpha_{S_t} \left[ 1 + \frac{1}{\Delta - 1} e^{-k} - \frac{\Delta}{\Delta -1} e^{- \frac{k}{\Delta}} \right] + \beta_{S_t} \left[\frac{1}{\Delta-1} \left( e^{-\frac{k}{\Delta}} - e^{-k} \right) \right]  & \ge & \delta 
\end{eqnarray} \\ 
If we set $\beta_{S_t} = \Delta$, and using a second order Taylor approximation $e^{-\frac{2}{\Delta}} < 1 - \frac{2}{\Delta} + \frac{2}{\Delta^2}$

\begin{eqnarray}
\alpha_{S_t} [ 1 + \frac{1}{\Delta - 1} e^{-k} - \frac{\Delta}{\Delta -1} e^{-\frac{k}{\Delta}}] + \Delta [ \frac{1}{\Delta -1} (e^{-\frac{k}{\Delta}} - e^{-k})]   &>& 1\\
\alpha + \frac{\alpha}{\Delta - 1} e^{-k} - \alpha \frac{\Delta}{\Delta -1} e^{-\frac{k}{\Delta}} + \frac{\Delta}{\Delta - 1} e^{-\frac{k}{\Delta}} - \frac{\Delta}{\Delta - 1} e^{-k} &>& 1\\
(\alpha - 1) - \frac{\Delta}{\Delta - 1} e^{-\frac{k}{\Delta}} (\alpha - 1) - \frac{e^{-k}}{\Delta -1} (\Delta - \alpha) &>& 0 
\end{eqnarray}

for $k=2$, (20) will be true if:

\begin{eqnarray}
(\alpha - 1) \left[ 1 - \frac{\Delta}{\Delta - 1} (1 - \frac{2}{\Delta}) \right] - \frac{e^{-k}}{\Delta - 1}(\Delta - \alpha) &>& 0 \\
(\alpha - 1)\left[\frac{\Delta - 2}{\Delta * (\Delta -1)}\right] - \frac{\Delta - \alpha}{\Delta - 1} e^{-2} &>& 0 \\
(\alpha - 1)(\Delta - 2) - \frac{\Delta^2}{e^2} + \frac{\alpha \Delta}{e^2} &>& 0 \\
\alpha &>& \frac{ \frac{\Delta^2}{e^2} + (\Delta - 2)}{(\Delta -2) + \frac{1}{e^2}}
\end{eqnarray}

For some $\epsilon$ and any subset of $G$ such that $|V(S)| < \epsilon n$, the expansion property of $G$ guarantees that we can find an $\alpha > \frac{ \frac{\Delta}{e^2} + 1}{ 1 + \frac{1}{e^2}}$, thus proving the lemma.    

%Via a result cited in [Kahale 1995], it is known that for random $\Delta$-regular graphs, for every $\alpha < \Delta - 1$, $\exists \epsilon%$ s.t. with high probability all the subsets $S \subseteq V(G)$ s.t. $|S| \le \epsilon n$ have vertex expansion of at least $\alpha$. Setting $\alpha = \beta < \Delta -1$ and $k = 2$ in equation (15) gives us values greater than one for $\Delta \ge 4$. 
\end{proof}
\end{lm1} 
To establish growth of $S_t$ with high probability, we need to use a martingale argument, which we state and prove in the following lemma:

%%%%%% Lemma 2.2 %%%%%%%%

\newtheorem{lm2}[lm1]{Lemma}
\begin{lm2}
With high probability, $|S_{t+1}| = E[|S_{t+1}|] \pm O(\sqrt{N(S_t)})$.
\begin{proof}

For any time step t, arbitrarily order the pebbles (after splitting but before hopping) in $S_t$ using $i$ as an index over $\{1,\dots,2k\}$ for $k = |S_t|$. Define $(Z_i)^2k_1$ as the sequence of events such that $Z_i$ is a random variable that indicates which vertex is the destination of pebble $i$ at time $t+1$ For each timestep, define filter $\mathcal{F}$ as the increasing sequence of $\sigma$-fields $\mathcal{F}_0 \subseteq \mathcal{F}+1 \ldots \subseteq \mathcal{F}_n$ over the probability space of the marked neighbors of $N(S_t)$ and associate each $\mathcal{F}_i$ with $Z_1,\ldots,Z_i$. Let function $f$ be the function that calculates the total number of marked nodes at time $t+1$ in $N(S_t)$, and $\forall i \in \{1,\ldots,n\}$ let $A = f(Z_1,\ldots,Z_n)$. Then $X_j = E[A|Z_1,\ldots Z_j]$ is the Doob martingale of A. Since $X_j - X_{j-1}$ is bounded by at most 1, Azuma's inequality gives us:  
\begin{eqnarray}
\Pr[|S_{t+1}| - \delta |S_t| \ge \tau |S_t|] &\le& exp(-\frac{\tau^2  |S_t|^2}{ 4|S_t|}) \\
&=& exp(-\frac{\tau^2 |S_t|}{4})
\end{eqnarray}

To prove that our process can get the size of the marked set up to size $\epsilon n$ in $\log n$ steps using the martingale bound just established above, consider a Markov process in which the $|S_t|$'s act as the state spaces. Transitions occur as follows: with probability $ 1 - exp(-\frac{\tau^2  |S_t|^2}{ 4|S_t|})$ the state space will go from size $|S_t|$ to size to  $(\delta - \tau)|S_t|$. With probability $exp(-\frac{\tau^2  |S_t|^2}{ 4|S_t|})$ the size of the marked set will decrease all the way to 1, a conservative over-estimate.

First, it should be clear that with some small but constant probability we can arrive at $|S_t| = C$, where $C$ is some adjustable constant that we will be able to tune. Once that happens, we want to show that for $C$ sufficiently large, a walk that is at $|S_t| = C$ will  reach $|S_t| = \epsilon n$, with $\Pr \ge \frac{1}{2}$. Setting $r = \frac{\tau^2}{4}$ and letting $(\delta - \tau) = (1 + \tau^*)$, observe that a failure will occur with probability :
\begin{eqnarray}
\Pr [\text{Fail}] &\le& e^{-r C} + e^{-r (1 + \tau^*) C} + e^{-r (1+ \tau^*)^2 C} + \dots + e^{-r (1 + \tau^*)^N C}\\
&\le& e^{-r C} +  e^{-r (1 + \tau^*) C} + e^{-r (1 + 2 \tau^*) C} + \dots + e^{-r (1 + N \tau^*) C} \\
&\le& e^{-r C} \times (1 + e ^{-r \tau^* C} + e^{-r 2 \tau^* C} + \dots + e^{-r N \tau^* C} \\
&=& \frac{e^{-r C}}{1 - e^{-r \tau^* C}} \\
&\le& \frac{1}{2} 
\end{eqnarray}
when C is sufficiently large, depending on the value of $\tau$. We can easily achieve our result w.h.p. in $\log^2 n$ time by repeating each such walk described above $O(\log n)$ times. However, we can actually do better and achieve an $\Omega(\log n)$ bound. If we view each walk as a trial, we know that there are at most $b \log n$ failed trials before we have a trial that is successful, for some constant b. Label a $|S_t|$ growth step as a heads in a coin flip and a $|S_t|$ shrink step/failure as a tails.  Each trial then consists of some number (possibly zero) of heads followed by a single tails flip. Given that we have $O(\log n)$ failed trials before we have a successful run, we know that there are $O(\log n)$ tails in our "failure block". However, w.h.p. there are $\Omega ( \log n)$ heads in this block as well, as the following argument shows.

We would like to bound the probability of heads from above, by some probability $\hat{p}$. To do this we will create another process, $P_{m+1}$ which dominates the current process, $P_m$. $P_{m+1}$ has the same state-space and transition arrows as $P_m$, but its transition probabilities are rewritten as follows: given that we are at state $i$ of size $(1+\tau^I)^i$, the probability of transitioning to a state with size $(1+\tau^*)^{i+1}$ in the next step, 
\begin{equation} 
\Pr \text{[growth]} = 1 - e^{-r(1+i\tau^*)} 
\end{equation}
and the probability transitioning to state with size = 1 is:
\begin{equation}
\Pr[\text{shrink}] = e^{-r(1+i\tau^*)}
\end{equation}
It is easy to see that the probability of growing is now lower than in $P_m$, and the the probability of shrinking is greater (formal proof can be found in the appendix on dominance). We would now like to compute an upper bound on the probability of growing conditioned on being in a trial that ends in a failure (i.e. shrinking all the way back to 1). Formally, we want to calculate $\Pr[i^{th}$ step = growth $| i-1$ steps were growth steps and shrinking occurs at step $k \ge i$]. But this is equal to $1 - \Pr$[$i^{th}$ step shrinks $| i-1$ growth steps and shrinking at $k \ge i$ steps]. This is:
\begin{eqnarray}
& = & \frac{e^{-r(1 + i\tau^*)}}{\sum_{l=i}^{k'} \left[ \prod_{j = i}^{l-1} (1-e^{-r(1+j\tau^*)}) \right] e^{-r(1+l \tau^*)}} \\
& \ge &  \frac{e^{-r(1 + i\tau^*)}}{\sum_{l=i}^{k'} e^{-r(1+l \tau^*)}} \\ 
& \ge & \frac{e^{-r i \tau^*}}{\sum_{l=i}^{k'} e^{-r l  \tau^*}} \\
& \ge & \frac{1}{\sum_{j = 0}^{\infty} e^{-r j \tau^*}}\\
& = & 1 - e^{-r \tau^*} 
\end{eqnarray}
where $k'$ is $\sup k$ s.t. $k < \log n$. Thus the conditional probability of growth $ \le e^{-r \tau^*}$, giving us what we needed,  an upper bound on the probability of growth at any step. Now we can apply a Chernoff bound on the number of growth steps needed to achieve a successful run. Assume now that our inequality above is tight and let the probability that we get a growth step be $\hat{p} = e^{-r\tau^*}$. Let us consider a run of $c \log n / \hat{p}$ steps. Letting $X_i$ be a random variable representing the outcome of the $i^{th}$ step, equal to 1 if that step is a growth and 0 otherwise, and letting $X = \sum X_i$, then $E[X] = c \log n$. Applying a Chernoff bound, we have: 
\begin{equation}
\Pr[|X - c \log n | \ge \epsilon c \log n] \le e^{-\frac{\epsilon^2}{3} c \log n}
\end{equation}.

Thus w.h.p there are $\Omega(\log n)$ heads and $O(\log n)$ tails until we get a run of $\log n$ heads. Translating back to our original model. This means that with $\Pr[growth] \ge \hat{p}$, we also have shown that given $O(\log n)$ failed trials, the combined number of successful and unsuccessful hops is $O(\log n)$, thus proving our result.
\end{proof}   
\end{lm2}

\subsection{Phase 2} 
In the previous phase we have shown that with each time step, with high probability the size of the marked set is growing by a factor larger than one. Thus, also with high probability, after $\Omega(\log n)$ steps we have grown to marked set of size $\epsilon n$. This threshold exists, recall, because of the claims we made about the $\alpha$ and $\beta$ of any subset of $V(G)$ of size $\le \epsilon n$ for some value of $\epsilon$ not dependent on $n$. Once we have hit this threshold, we need a different argument to show not that the marked set is still growing, but that we will cover all of the vertices of$G$ in $O(\log^2 n)$ steps. However, we want to do this in a way so as not to have to keep track of the complex interactions of the walks as they branch out, collide, coalesce, and branch out again. 

We introduce a weaker but related random process, $R_{alt}$, which will take longer than our generalized random walk and therefore be dominated by it. This process will have an $O(\log^2 n)$ bound, meaning that our original process will also have an $O(\log^2 n)$ bound on cover time. 

\subsubsection{Description of $R_{alt}$}

	For this process, we have the same exact graph, G, as in our original process. Each of the $\epsilon n$ marked nodes has its own individual pebble to start. At each time step, each pebble choses a neighbor of the node it is currently located at and moves to it as follows:
\begin{itemize}
\item If there are no pebbles at a node, clearly nothing happens. \\
\item If there is one pebble at a node, the pebble choses a neighbor with probability $\frac{1}{d}$. \\
\item If there are two pebbles at a node, arbitrarily pick one pebble as the "leader". This pebble choses a neighbor to move to again with probability $\frac{1}{d}$. The second pebble, with probability $\frac{1}{2}$, picks the same neighbor as the lead pebble. With probability $\frac{1}{2}$ it independently chooses a neighbor; thus, each neighbor not chosen by the first pebble is chosen with probability $\frac{1}{2d}$.  \\
\item If there are more than two pebbles, we again arbitrarily pick a leader pebble, a second pebble, and so on until we have assigned a ranking to each pebble. The first two pebbles select neighbors as described in the 2-pebble case. The remaining pebbles choses one of the already-selected neighbors, each with probability $\frac{1}{2}$. 
\end{itemize}
Note that if a node has one pebble, behavior of $R_{alt}$ is identical to the original process. If there are two pebbles, the probability that the two pebbles will end up at the same neighbor in the next time step is $\frac{1}{2} + \frac{1}{2d}$, which is greater than the probability of the same event occurring in our original process, $\frac{1}{d}$. When there are three or more pebbles, $R_{alt}$ behaves similarly to the original process in the sense that only a maximum of two neighbors are selected and all pebbles must end up at one of those neighbors. Like the case with only two pebbles at a node, however, there is an elevated probability that all pebbles will go to the same neighbor. $R_{alt}$ is a weaker process because of this elevated probability of selecting the same neighbor twice -- by duplicating walks, the pebbles cover in expectation fewer nodes at each time step and therefore take longer to cover the entire graph. 

\subsubsection{Analysis of $R_{alt}$}


%%%%%% Theorem 2.2 %%%%%%%%%

\newtheorem{th2}[th1]{Theorem}\begin{th2}
For $\Delta$-regular random expander graph $G$ with $\lambda_2 < \frac{1}{2}$ and $\epsilon n$ pebbles on the vertices of $G$, the cover time of $R_{alt}$ on $G$ is $O(\log^2 n)$. 
\begin{proof} If we can show that each vertex in $G$ is covered with constant probability in $\Theta(\log n)$ steps, then the theorem follows by carrying out $O(\log n)$ phases of $\Theta(\log n)$ steps each. Let $E_i$ be the event that pebble $i$ covers an arbitrary vertex $v$ in $s$ steps. We are interested in $\Pr \bigcup_i E_i]$, the probabilty that $v$ is covered by at least one pebble. To analyze this, we use a second-order approximation:
\begin{equation}
\Pr [\bigcup_i E_i] \ge \sum_i \Pr [E_i] - \sum_{i \neq j} \Pr [E_i \cap E_j] = \sum_i \Pr [E_i] - \sum_{i \ne j} \Pr[E_i]\Pr[E_j|E_i]
\end{equation}
Essentially we need to show that the second-order term is very small, and to do this we need to analyze the conditional walk of pebble $j$ given the fixed walk of pebble $i$. Each term $\Pr[E_i]$ is $\le O(\frac{1}{n})$, since at the end of phase 2, each pebble has a probability of being at any particular node equal to the value of the vertex's component of the stationary distribution vector, $\frac{1}{n}$. From [Alon et al 2010], the probability that an independent walk of pebble $i$ of length $O(\log n)$ deviates from $\frac{1}{n}$ by at most $\frac{1}{2n}$. 

To bound $\Pr[E_j|E_i]$, fix the walk of pebble $i$. Based on the rules of transition for $R_{alt}$, pebble $j$ follows the modified transition matrix $(M + T_{l(i),t})$, where $M$ is the standard transition matrix for G, and $T_{l(i),t}$ is a matrix depending on the vertex location of $i$ at time t, viewed as the function $l(i)$.  The columns,  $(M + T_{l(i),t})_k$ are identical to M for $k \ne l(i)$. For $k = l(i)$, the entries of the column are $\frac{1}{2} + \frac{1}{2d}$ for one randomly selected entry that is $\frac{1}{d}$ in M, and the rest of the entries are $\frac{1}{2d}$. From any probability distribution $z$ over $V(G)$, it is clear that that after $s = O(\log n)$ steps the probability of pebble $j$ being a vertex $v$ is the corresponding component of the vector $z  \prod^s_{t=1}(M + T_{l(i),t})$. By Lemma 3 below, $z \prod^s_{t=1}(M + T_{l(i),t}) < \frac{2}{n}$. Thus, 
\begin{eqnarray*}
\Pr(\bigcup E_i) &\ge& \sum_i P(E_i) - \sum_{i \ne j} P(E_i)P(E_i | E_j) \\
&\ge& \epsilon n \frac{1}{n} - \binom{\epsilon n}{2} \frac{2}{n^2} \\
&\ge& \epsilon - \epsilon^2
\end{eqnarray*}
and the theorem follows. 
 \end{proof}
\end{th2}

%%%%% Lemma 2.3 %%%%%%%%%
\newtheorem{lm3}[lm1]{Lemma}
\begin{lm3} For $z$ a probability distribution over $V(G)$, and $(M+T_{l(i),t})$ a family of transition operators on V(G) over a fixed sequence $\{l(i),t\} \text{ for } t \in \{1, \dots, s\}$, each component of  $z \cdot  \prod_{t = 1}^{s} (M+T_{l(i),t}) < \frac{2}{n}$. 
\begin{proof}
Let $z = u + x$, where $u$ is the uniform distribution over $V(G)$ and $x$ is a vector such that $\sum x_i = 0$. Then $z \cdot \prod_{t = 1}^{s} (M+T_{l(i),t}) = x \cdot \prod_{t=1}^s (M+T_{l(i),t}) + u \cdot \prod^s_{t=1} (M+T_{l(i),t})$. 

First we prove that each component of $x \cdot \prod_{t=1}^s (M+T_{l(i),t})$ can be made vanishingly small, by proving that its norm,  
\begin{equation} 
 \Vert x \cdot \prod_{t=1}^s (M+T_{l(i),t}) \Vert \le (\lambda_2 + \frac{1}{2})^s \Vert x \Vert 
\end{equation}
by induction.   Consider just one step: $x \cdot (M + T_{l(i),t}) = x \cdot M + x \cdot T_{l(i),t}$ for some arbitrary value of $l(i)$. Because $x \perp u$, we know from the property of expanders that since $\lambda_2 = \text{max}_{x\perp u}  \frac{\Vert xM \Vert}{\Vert x \Vert}$, $\Vert xM \Vert \le \lambda_2 \Vert x \Vert$.  For the second part, we have $\Vert x \cdot T_{l(i),t} \Vert  = (x_{l(i)_1} \frac{-1}{2d})^2 + \dots +  (x_{l(i)_2} \frac{-1}{2d})^2 + (x_{l(i)_d} \frac{d-1}{2d})^2 \le \frac{1}{2} \Vert x \Vert$.

Using this argument, we see that the terminal case holds. Now assume that the relation holds for the case of $s-1$. Consider the vector $ x \cdot \prod_{t = 1}^{s-1} (M + T_{l(i),t})$. Note that this vector is also a probability distribution and that since $\prod_{t=1}^{s-1} (M+T_{l(i),t})$ is also a stochastic matrix, the product is also a probability vector and is orthogonal to $u$. As such, it is just another $x$, and invoking the inductive hypothesis we prove the result about the norm.

Finally, we want to show that each component of $u \cdot \prod_{t=1}^s (M+T_{l(i),t}) < \frac{2}{n}$. Consider our arbitrary path $v_0 \rightarrow v_1 \rightarrow \ldots \rightarrow v_s$. Start a pebble walking from a vertex drawn from the stationary distribution $u$. Define $p_j(v_i)$ as the probability of a pebble being at vertex $i$ at time step $j$. We want to show that the probability of being at any vertex in G after s time steps is less than $\frac{2}{n}$. We have that $\forall v, p_0(v) = \frac{1}{n}$. We claim that for all vertices along the fixed path, $p_k(v_k) \le \frac{2}{n}$, and that $p_k(v) \le \frac{1}{n}$ for $v \notin \{v_0,\ldots, v_s\}$.

The first claim, $p_k(v_k) \le \frac{2}{n}$, is proved by induction. We will show that $p_j \le \frac{1}{n}(1 + \frac{1}{2} + \frac{1}{2^2} + \dots + \frac{1}{2^j})$. For the base case, $p_1(v_1) = \frac{1}{n}(\frac{1}{2} + \frac{1}{2}) + \frac{1}{n}(\frac{d-1}{d}) = \frac{1}{n}(2 - \frac{1}{2d}) \le \frac{2}{n}$. For the inductive case, we have 
\begin{eqnarray*}
p_{j+1}(v_{j+1}) &\le& p_j(v_j) (\frac{1}{2} + \frac{1}{2d}) + \frac{1}{n} \frac{d-1}{d}. \\
&\le& \frac{1}{n} (1 + \frac{1}{2} + \dots + \frac{1}{2^j})(\frac{1}{2} + \frac{1}{2d}) + \frac{1}{n} \frac{d-1}{d} \\
&=& \frac{1}{n} (\frac{1}{2} + \frac{1}{4} + \dots + \frac{1}{2^{j+1}} + \frac{1}{n} + \frac{1}{dn} (\frac{1}{2}+ \frac{1}{4} + \dots + \frac{1}{2^{j+1}}) -  \frac{1}{dn}\\
&\le& \frac{1}{n}(1 + \frac{1}{2} + \dots + \frac{1}{2^{j+1}})
\end{eqnarray*}

The second claim has two cases: the first is that v is a neighbor of vertex along the path, $v_j$. Then $p_{j+1}(v) \le \frac{1}{2d} p_j(v_j) + \frac{d-1}{d} \frac{1}{n} \le \frac{1}{n}.$

Finally, if v is not a neighbor of $v_j$, then we have $p_{j+1}(v) \le \frac{1}{n}$

\end{proof}

\end{lm3}


\end{document}
